﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PriorityQueue
{
    class PriorityQueue<T> : IEnumerable<T>
        where T : IComparable<T>
    {

        private T[] heap;
        private int capacity;
        private IComparer<T> comparer;
        private int lastElement;

        class DefaultTComparer : IComparer<T>
        {

            public int Compare(T x, T y)
            {
                return x.CompareTo(y);
            }
        }

        public PriorityQueue()
            : this(new DefaultTComparer())
        {
            
        }

        public PriorityQueue(IComparer<T> comparer)
        {
            lastElement = 0;
            capacity = 1024;
            heap = new T[capacity];
            this.comparer = comparer;
        }

        public void Enqueue(T newElem)
        {
            heap[lastElement++] = newElem;

            int cIndex = lastElement - 1;
            int pIndex = GetParent(cIndex);
            while (cIndex > 0 && heap[cIndex].CompareTo(heap[pIndex]) > 1)
            {
                T temp = heap[cIndex];
                heap[cIndex] = heap[pIndex];
                heap[pIndex] = temp;
                cIndex = pIndex;
                pIndex = GetParent(cIndex);
            }
        }

        private int GetParent(int index)
        {
            if ((index & 1) == 0)
            {
                return (index >> 1) - 1;
            }
            return (index >> 1);
        }

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}
